package org.example.myleet.rosalind.sort;

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
//        int[] pi = parseStringToArr("1 2 3 4 5 6 7 8 9 10");
//        int[] sigma = parseStringToArr("1 8 9 3 2 7 6 5 4 10");
//        int[] pi = parseStringToArr("1 2 3 4 5 6 7 8 9 10");
//        int[] sigma = parseStringToArr("3 1 5 2 7 4 9 6 10 8");
//        int[] pi = parseStringToArr("3 9 10 4 1 8 6 7 5 2");
//        int[] sigma = parseStringToArr("2 9 8 5 1 7 3 4 6 10");
        int[] pi = parseStringToArr("9 1 2 8 5 4 10 3 6 7");
        int[] sigma = parseStringToArr("7 5 3 2 9 8 4 1 6 10");
        solution.findReversalDistancePath(pi.length, pi, sigma);
    }

    private static int[] parseStringToArr(String line) {
        String[] parts = line.split(" ");
        int[] arr = new int[parts.length];
        for (int i = 0; i < arr.length; ++i) {
            arr[i] = Integer.parseInt(parts[i]);
        }
        return arr;
    }

    public void findReversalDistancePath(int n, int[] pi, int[] sigma) {
        if (isSame(pi, sigma)) {
            System.out.print("0\n");
            return;
        }
        //记忆化搜索，分别是到达某种排列时的步数，和路径
        Map<String, Integer> memo1 = new HashMap<>();
        Map<String, List<String>> memoPath1 = new HashMap<>();
        //from pi to sigma
        Queue<Step> queue = new LinkedList<>();
        Step step = new Step(copyArr(pi), new ArrayList<>());
        queue.add(step);
        memo1.putIfAbsent(arrToString(step.arrangement), 0);
        while (!queue.isEmpty()) {
            //BFS方式，将每一步产生的子数组翻转结果用于下一步搜索
            //从队列中弹出下一步
            step = queue.poll();
            //从记忆中找到上一步的翻转次数
            Integer reversalCount = memo1.get(arrToString(step.arrangement));
            ++reversalCount;
            for (int l = 1; l < n; ++l) {
                for (int s = 0; s + l < n; ++s) {
                    //产生下一步
                    int[] newArr = copyArr(step.arrangement);
                    reverse(newArr, s, s + l);
                    if (isSame(sigma, newArr)) {
                        //找到，输出结果后退出
                        System.out.printf("%d\n", reversalCount);
                        //按正向顺序输出结果
                        for (String p : step.path) {
                            System.out.println(p);
                        }
                        System.out.println(s + 1 + " " + (s + l + 1));
                        return;
                    }
                    String newArrStr = arrToString(newArr);
                    if (!memo1.containsKey(newArrStr)) {
                        memo1.put(newArrStr, reversalCount);
                        List<String> path = new ArrayList<>(step.path);
                        path.add(s + 1 + " " + (s + l + 1));
                        memoPath1.put(newArrStr, path);
                        if (reversalCount < 5) {
                            //！注意，参考高手的解法中使用了双向搜索的技巧，将45^10复杂度降到45^5使暴力BFS变成可能
                            Step nextStep = new Step(newArr, step.path);
                            //将本次步骤加入到路径中
                            nextStep.path.add(s + 1 + " " + (s + l + 1));
                            queue.add(nextStep);
                        }
                    }
                }
            }
        }
        //try from sigma to pi
        //反向做一样的搜索
        int ans = 1000;
        Map<String, Integer> memo2 = new HashMap<>();
        step = new Step(copyArr(sigma), new ArrayList<>());
        queue.add(step);
        memo2.putIfAbsent(arrToString(step.arrangement), 0);
        List<String> shortestPath = new ArrayList<>();
        while (!queue.isEmpty()) {
            step = queue.poll();
            Integer reversalCount = memo2.get(arrToString(step.arrangement));
            ++reversalCount;
            for (int l = 1; l < n; ++l) {
                for (int s = 0; s + l < n; ++s) {
                    int[] newArr = copyArr(step.arrangement);
                    reverse(newArr, s, s + l);
                    if (isSame(pi, newArr)) {
                        //找到了，也可以结束，输出结果后退出
                        System.out.printf("%d\n", reversalCount);
                        //因为是从sigma到pi，因此输出到步骤应该反向（反向操作）
                        System.out.println(s + 1 + " " + (s + l + 1));
                        for (int i = step.path.size() - 1; i >= 0; --i) {
                            System.out.println(step.path.get(i));
                        }
                        return;
                    }
                    String newArrStr = arrToString(newArr);
                    Integer fromPi = memo1.get(newArrStr);
                    if (null != fromPi) {
                        //反向搜索中遇到正向搜寻的路径，打通了其中一条翻转的路径，但不知道是不是最优的，先记录下来
                        if (fromPi + reversalCount < ans) {
                            ans = fromPi + reversalCount;
                            //记录操作步骤的方法为正向操作（fromPiPath）+逆向操作
                            List<String> fromPiPath = memoPath1.get(newArrStr);
                            shortestPath = new ArrayList<>(fromPiPath);
                            shortestPath.add(s + 1 + " " + (s + l + 1));
                            for (int i = step.path.size() - 1; i >= 0; --i) {
                                shortestPath.add(step.path.get(i));
                            }
                        }
                    }
                    if (!memo2.containsKey(newArrStr)) {
                        memo2.put(newArrStr, reversalCount);
                        if (reversalCount < 4) {
                            Step nextStep = new Step(newArr, step.path);
                            nextStep.path.add(s + 1 + " " + (s + l + 1));
                            queue.add(nextStep);
                        }
                    }
                }
            }
        }
        //将最短的操作路径输出后退出
        System.out.printf("%d\n", ans);
        for (String p : shortestPath) {
            System.out.println(p);
        }
    }

    private String arrToString(int[] arr) {
        StringBuilder sb = new StringBuilder(arr.length * 2);
        for (int i = 0; i < arr.length; ++i) {
            sb.append(arr[i]).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }

    private int[] copyArr(int[] arr) {
        int[] copy = new int[arr.length];
        System.arraycopy(arr, 0, copy, 0, arr.length);
        return copy;
    }

    private boolean isSame(int[] arr1, int[] arr2) {
        for (int i = 0; i < arr1.length; ++i) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    /**
     * Reverse an interval of an array, include start and end
     * @param arr array
     * @param start include
     * @param end include
     * @return Reverse the interval from start to end on the original array
     */
    private void reverse(int[] arr, int start, int end) {
        while (start < end) {
            int t = arr[start];
            arr[start] = arr[end];
            arr[end] = t;
            ++start;
            --end;
        }
    }

    static class Step {
        int[] arrangement;
        List<String> path;

        public Step(int[] arrangement, List<String> path) {
            this.arrangement = arrangement;
            this.path = new ArrayList<>(path);
        }
    }
}
